/*
2976. 转换字符串的最小成本 I
已解答
中等
相关标签
相关企业
提示
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。

另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z  、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。

返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

 

示例 1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将字符串 "abcd" 转换为字符串 "acbe" ：
- 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。
- 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。
- 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。
- 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。
可以证明这是可能的最小成本。
示例 2：

输入：source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
输出：12
解释：要将字符 'a' 更改为 'b'：
- 将字符 'a' 更改为 'c'，成本为 1 
- 将字符 'c' 更改为 'b'，成本为 2 
产生的总成本是 1 + 2 = 3。
将所有 'a' 更改为 'b'，产生的总成本是 3 * 4 = 12 。
示例 3：

输入：source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
输出：-1
解释：无法将 source 字符串转换为 target 字符串，因为下标 3 处的值无法从 'd' 更改为 'e' 。
 

提示：

1 <= source.length == target.length <= 105
source、target 均由小写英文字母组成
1 <= cost.length== original.length == changed.length <= 2000
original[i]、changed[i] 是小写英文字母
1 <= cost[i] <= 106
original[i] != changed[i]
*/

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

class Solution {
public:
    template<class T>
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        // 定义二维数组 dis 存储任意两个小写字母间的最短转换成本
        int dis[26][26];
        // 初始化为无穷大
        memset(dis, 0x3f, sizeof(dis));
        // 自身到自身的转换成本为 0
        for (int i = 0; i < 26; ++i) {
            dis[i][i] = 0;
        }

        // 遍历所有给定的转换规则
        for (int i = 0; i < cost.size(); ++i) {
            // 若转换的源字符和目标字符相同，无需更新
            if (original[i] == changed[i]) continue;
            int x = original[i] - 'a';
            int y = changed[i] - 'a';
            dis[x][y] = min(dis[x][y], cost[i]);
        }

        // 使用 Floyd - Warshall 算法计算任意两个字母间的最短转换成本
        for (int k = 0; k < 26; ++k) {
            for (int i = 0; i < 26; ++i) {
                // 若 dis[i][k] 为无穷大，跳过后续计算
                if (dis[i][k] == 0x3f3f3f3f) continue;
                for (int j = 0; j < 26; ++j) {
                    // 若 dis[k][j] 为无穷大，跳过本次更新
                    if (dis[k][j] != 0x3f3f3f3f) {
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                    }
                }
            }
        }

        // 初始化总成本为 0
        long long ans = 0;
        // 遍历 source 和 target 字符串
        for (int i = 0; i < source.length(); ++i) {
            int d = dis[source[i] - 'a'][target[i] - 'a'];
            // 若无法转换，返回 -1
            if (d == 0x3f3f3f3f) return -1;
            ans += d;
        }
        return ans;
    }
};